「譬如為山，未成一簣，止，吾止也；譬如平地，雖覆一簣，進，吾往也。」 ——孔子

哪怕山虧一簣，也謂丘陵，望遠足矣。你們跟著我堅持到今天，走過了一半的路程，你們已和路邊隨處可見的雜魚不同，大可引以為傲。我相信是你們的話，一定能和我一起征服diff算法！

回顧需求

我們距離完成/src/runtime-core/renderer.ts只剩最後一步，也就是當新舊節點都有多個dom元素的子節點時，我們必須一一比對這些子節點哪些有產生改變，並最少量更新它們。這樣說可能有點抽象，就來看個例子吧。

<template>
  <ul>
    <li v-for="item in list" :key="item.id">{{ item.name }}</li>
  </ul>
</template>

<script lang="ts" setup>
import { reactive } from 'vue'

const list = reactive([
  { id: 1, name: 'A' },
  { id: 2, name: 'B' },
  { id: 3, name: 'C' },
  { id: 4, name: 'D' },
  { id: 5, name: 'E' }
])

setTimeout(()=>{
  list.splice(2, 1, { id: 25, name: 'Y' }, { id: 26, name: 'Z' })
}, 5000)
</script>

我們可以看到，對ul標籤的虛擬dom來說，它的子節點li們產生了改變，從（方便起見，我們將list的每一項用它們的name屬性來簡稱）ABCDE改成了ABYZDE。在這個範例中，ABDE的標籤名都是li，且key都沒有改變，因此這四個li標籤是不需要重新渲染的；而原本的C被改成了YZ，儘管都是li標籤，但key完全不同，因此C必須被移除，並在C的位置重新渲染YZ。

diff算法的目的，就是為了找出刪除哪些dom元素、渲染哪些dom元素，能用最少量的dom元素操作，將dom元素更新成我們期望的樣子。也就是說，我們的目的就是找出需要被刪除及渲染的節點。

比對頭尾

我們拿來跑v-for的陣列可能會在尾端push資料（例如像fb文章的瀑布流），也可能往首項unshift資料（例如剛發表的最新文章），也可能給中間一項改變一些屬性（例如編輯文章），這些常見的陣列操作，通常都不會動到首、尾或者首 + 尾。因此我們可以先比對新舊子節點的首是從第幾項開始不同、尾又是從第幾項開始不同。

所以我們先在/src/runtime-core/renderer.ts的patch中補上patchKeyedChildren方法如下：

const patchKeyedChildren = (oldChildren: VNode[], newChildren: VNode[], el: HTMLElement) => {
  let pointer = 0;
  let oldEnd = oldChildren.length - 1;
  let newEnd = newChildren.length - 1;
  // 從開頭找相同子節點
  while (pointer <= oldEnd && pointer <= newEnd) {
    const oldNode = oldChildren[pointer];
    const newNode = newChildren[pointer];
    if (isSameVnode(oldNode, newNode)) patch(oldNode, newNode, el);
    else break;
    pointer++;
  }
  // 從結尾找相同子節點
  while (pointer <= oldEnd && pointer <= newEnd) {
    const oldNode = oldChildren[oldEnd];
    const newNode = newChildren[newEnd];
    if (isSameVnode(oldNode, newNode)) patch(oldNode, newNode, el);
    else break;
    oldEnd--;
    newEnd--;
  }
};

先宣告一個pointer指針，並記錄舊子節點和新子節點的末項。

let pointer = 0;
let oldEnd = oldChildren.length - 1;
let newEnd = newChildren.length - 1;

然後遍歷新舊子節點（以下簡稱為新子及舊子），遞歸調用patch方法比對新、舊子的屬性及孫節點，直到遇到新、舊子不相同的情況。

while (pointer <= oldEnd && pointer <= newEnd) {
  const oldNode = oldChildren[pointer];
  const newNode = newChildren[pointer];
  if (isSameVnode(oldNode, newNode)) patch(oldNode, newNode, el);
  else break;
  pointer++;
}

尾端也如法炮製，當遍歷完後，我們成功遞歸調用了patch方法去比對新、舊子的首、尾的屬性及孫節點，此時我們能確保新、舊子的首、尾應該都是相同的。大概是以下這種感覺：

• 舊：AB(C)DE
• 新：AB(YZ)DE

除了括號內的C應該改成YZ，其首尾的A、B、D、E都已比對完成，在不渲染它們的情況下將實體dom元素節點的屬性及孫節點更新完畢。

比對中間節點

首尾節點已經不用再看了，接下來我們要先確認新、舊子中間是否還有剩下來尚未比較的節點。
我們可以分成以下四種情況進行討論：

新子沒剩舊子沒剩就甚麼事都不用做，所以可以不用管它。
接著讓我們把新子有剩舊子沒剩、新子沒剩舊子有剩這兩種比較簡單的情況寫出來吧：

if (pointer > oldEnd) {
  // 新子有剩舊子沒剩，則創建剩餘新子
  while (pointer <= newEnd) {
    const nextPosition = newEnd + 1;
    const anchor = nextPosition < newChildren.length ? newChildren[nextPosition].el : null;
    patch(null, newChildren[pointer], el, anchor);
    pointer++;
  }
} else if (pointer > newEnd) {
  // 新子沒剩舊子有剩，則刪除剩餘舊子
  while (pointer <= oldEnd) {
    unmount(oldChildren[pointer]);
    pointer++;
  }
} else {
  // ......
}

我們先看新子有剩舊子沒剩的情況。
當patch的第一個參數是null時，就會渲染這些dom元素。渲染新子沒甚麼爭議，但要給它們inserBefore到哪個dom元素節點之後呢？我們來改造一下之前舉的例子：

• 舊：AB()DE
• 新：AB(YZ)DE

我們比對完了首AB，也比對完了尾DE，接下來剩下新節點的YZ需要渲染，它們該insertBefore到哪？很明顯就是D的前面。

但如果是這種情況：

• 舊：AB()
• 新：AB(YZ)

YZ不需要insertBefore到任何節點的前方，儘管往後面插就是了。

所以用於insertBefore的節點anchor，就是這樣定出來的：

const anchor = nextPosition < newChildren.length ? newChildren[nextPosition].el : null;

然後有多的新子就渲染，有多的舊子就全幹掉。如此一來，便只剩下新子有剩舊子也有剩的最複雜的情況。

我們明天將會用最長遞增子序列算法，來解決這個最後的問題。

githubmain分支commit「[Day 17] runtime-core——diff算法」